<html>
 <head>
  <link href="./leetcode-problem.css" rel="stylesheet" type="text/css">
 </head>
 <body>
  <div class="question_difficulty">
   难度：Medium
  </div>
  <div>
   <h1 class="question_title">
    236. Lowest Common Ancestor of a Binary Tree
   </h1>
   <p>
    Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
   </p>
   <p>
    According to the
    <a href="https://en.wikipedia.org/wiki/Lowest_common_ancestor" target="_blank">
     definition of LCA on Wikipedia
    </a>
    : &ldquo;The lowest common ancestor is defined between two nodes p&nbsp;and q&nbsp;as the lowest node in T that has both p&nbsp;and q&nbsp;as descendants (where we allow
    <b>
     a node to be a descendant of itself
    </b>
    ).&rdquo;
   </p>
   <p>
    Given the following binary tree:&nbsp; root =&nbsp;[3,5,1,6,2,0,8,null,null,7,4]
   </p>
   <img alt="" src="https://assets.leetcode.com/uploads/2018/12/14/binarytree.png" style="width: 200px; height: 190px;">
   <p>
    &nbsp;
   </p>
   <p>
    <strong>
     Example 1:
    </strong>
   </p>
   <pre>
<strong>Input:</strong> root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
<strong>Output:</strong> 3
<strong>Explanation: </strong>The LCA of nodes <code>5</code> and <code>1</code> is <code>3.</code>
</pre>
   <p>
    <strong>
     Example 2:
    </strong>
   </p>
   <pre>
<strong>Input:</strong> root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
<strong>Output:</strong> 5
<strong>Explanation: </strong>The LCA of nodes <code>5</code> and <code>4</code> is <code>5</code>, since a node can be a descendant of itself according to the LCA definition.
</pre>
   <p>
    &nbsp;
   </p>
   <p>
    <strong>
     Note:
    </strong>
   </p>
   <ul>
    <li>
     All of the nodes' values will be unique.
    </li>
    <li>
     p and q are different and both values will&nbsp;exist in the binary tree.
    </li>
   </ul>
  </div>
  <div>
   <h1 class="question_title">
    236. 二叉树的最近公共祖先
   </h1>
   <p>
    给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
   </p>
   <p>
    <a href="https://baike.baidu.com/item/%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88/8918834?fr=aladdin" target="_blank">
     百度百科
    </a>
    中最近公共祖先的定义为：&ldquo;对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（
    <strong>
     一个节点也可以是它自己的祖先
    </strong>
    ）。&rdquo;
   </p>
   <p>
    例如，给定如下二叉树:&nbsp; root =&nbsp;[3,5,1,6,2,0,8,null,null,7,4]
   </p>
   <p>
    <img alt="" src="https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/15/binarytree.png" style="height: 190px; width: 200px;">
   </p>
   <p>
    &nbsp;
   </p>
   <p>
    <strong>
     示例 1:
    </strong>
   </p>
   <pre><strong>输入:</strong> root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
<strong>输出:</strong> 3
<strong>解释: </strong>节点 <code>5 </code>和节点 <code>1 </code>的最近公共祖先是节点 <code>3。</code>
</pre>
   <p>
    <strong>
     示例&nbsp;2:
    </strong>
   </p>
   <pre><strong>输入:</strong> root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
<strong>输出:</strong> 5
<strong>解释: </strong>节点 <code>5 </code>和节点 <code>4 </code>的最近公共祖先是节点 <code>5。</code>因为根据定义最近公共祖先节点可以为节点本身。
</pre>
   <p>
    &nbsp;
   </p>
   <p>
    <strong>
     说明:
    </strong>
   </p>
   <ul>
    <li>
     所有节点的值都是唯一的。
    </li>
    <li>
     p、q 为不同节点且均存在于给定的二叉树中。
    </li>
   </ul>
  </div>
 </body>
</html>